#include <iostream>


using namespace std;

class MyLinkedList {
public:
    // 定义链表节点结构体
    typedef struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){};
    }LinkedNode;

    MyLinkedList() {
        dummyHead = new LinkedNode(0);
        size = 0;
    }

    int get(int index) {
        if(index < 0 || index> size-1){
            return -1;
        }

        LinkedNode * curNode = dummyHead;
        for (int i = 0; i < index; ++i) {
            curNode = curNode->next;
        }

        return curNode->val;
    }

    void addAtHead(int val) {
        LinkedNode * newNode = new LinkedNode (val);
        newNode->next = dummyHead->next;
        dummyHead->next  = newNode;
        size++;
    }

    void addAtTail(int val) {
        //移动链表到最后一个节点
        LinkedNode * curNode = dummyHead;
        while (curNode->next!=NULL){
            curNode = curNode->next;
        }
        curNode->next = new LinkedNode (val);
        size++;
    }

    void addAtIndex(int index, int val) {
        if(index>size) return;
        if(index<0) index= 0;//创建头结点的意义就是为了将头结点普适化

        LinkedNode * newNode = new LinkedNode (val);
        LinkedNode * curNode = dummyHead;


        //for 循环中的i++ 和 ++i 是一样的
        //while 循环中的i++ 和 ++i 是不一样的
        //while 中 i++ 会先判断i的值，之后i再进行++运算；
        while (index--){
            curNode = curNode->next;
        }

        newNode->next = curNode->next;
        curNode->next = newNode;
        size++;
    }

    void deleteAtIndex(int index) {
        if(index < 0 || index> size-1){
            return;
        }

        LinkedNode * curNode = dummyHead;

        while (index--){
            curNode = curNode->next;
        }

        LinkedNode * temp = curNode->next;
        curNode->next = temp->next;
        delete temp;
        temp = nullptr;
        size--;
    }

    void printLinkList(){
        if(dummyHead== nullptr){
            std::cout<< "链表为空!"<< endl;
            return;
        }
        LinkedNode * cur = dummyHead->next;
        while (cur!=NULL){
            std::cout<< cur->val << "-> ";
            cur = cur->next;
        }
    }

public:
    int size ;
    LinkedNode * dummyHead;
};

int main0() {

    return 0;
}


/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */